package com.lisp.algorithm.book.c15;

public class LongestCommonSequence_topDown {

	public static void main(String[] args) {
		String s1 = "abced";
		String s2 = "dkanea";
		System.out.println(longestCommonSequence(s1, s2));
	}
	
	public static int longestCommonSequence(String text1, String text2) {
		int s1Len = text1.length(), s2Len = text2.length();
		int subSolution[][] = new int[s1Len+1][s2Len+1];
		for(int i=0; i<s1Len+1; i++) {
			for(int j=0; j<s2Len+1; j++) {
				if(i == 0 || j == 0) {
					subSolution[i][j] = 0;
				} else {					
					subSolution[i][j] = -1;
				}
			}
		}
		return longestCommonSequence(text1.toCharArray(), s1Len, 
				text2.toCharArray(), s2Len, subSolution);
	}
	
	private static int longestCommonSequence(char a[], int aEnd, 
			char b[], int bEnd, int[][] subSolution) {
		if(subSolution[aEnd][bEnd] != -1) {
			return subSolution[aEnd][bEnd];
		}
		
		if(a[aEnd-1] == b[bEnd-1]) {
			int solution =  1 + longestCommonSequence(a, aEnd-1, b, bEnd-1, subSolution);
			subSolution[aEnd][bEnd] = solution;
			System.out.println(String.format("subSolution[%s][%s] = %s", aEnd, bEnd, solution));
			return solution;
		} else {
			int x = longestCommonSequence(a, aEnd, b, bEnd-1, subSolution);
			int y = longestCommonSequence(a, aEnd-1, b, bEnd, subSolution);
			int solution =  x > y ? x : y; 
			subSolution[aEnd][bEnd] = solution;
			System.out.println(String.format("subSolution[%s][%s] = %s", aEnd, bEnd, solution));
			return solution;
		}
	}
}
